W6. Least Squares Geometry

1. Theory

1.1 The Least Squares Problem

In many real-world applications, we encounter systems of linear equations that have no exact solution. This happens when the system is overdetermined: there are more equations than unknowns (i.e., for an matrix ). For example, when fitting a line to 100 experimental data points, we have 100 equations but only 2 unknowns (slope and intercept). It is essentially impossible for any single line to pass through all 100 points exactly.

Rather than declaring defeat, we ask a better question: What is the best approximate solution? This is the least squares problem.

Definition (Least-Squares Solution): Given and , the least-squares solution is the vector that minimizes the residual norm:

where is the -th row of and is the -th entry of . The name “least squares” comes from the fact that we are minimizing the sum of squared errors between the predictions and the observations .

1.1.1 Motivating Example: Line Fitting

Suppose we want to find the best line through three points: , , . Substituting each point gives the system:

No single line passes through all three points (try it — you’ll get a contradiction). The least-squares approach finds the line that minimizes the total squared vertical distance from the data points to the line.

1.1.2 Applications

Least squares appears everywhere:

• Statistics: Linear regression (fitting models to data)
• Machine learning: Training linear models
• Physics and engineering: Fitting experimental data to theoretical models
• Signal processing: Filter design and system identification
• Economics: Estimating demand curves and cost functions
• Computer vision: Camera calibration and pose estimation

1.2 Geometric Interpretation: Projection onto the Column Space

The key geometric insight is this: always lies in the column space , no matter what we choose. If , then no exact solution exists. But we can still ask: what is the closest point in to ?

That closest point is the orthogonal projection of onto , denoted . The least-squares solution is exactly the vector satisfying .

The error vector is orthogonal to the entire column space . This orthogonality condition is the key to deriving the solution.

1.3 The Normal Equations

The orthogonality condition means is orthogonal to every column of . Since the columns span , this is equivalent to:

Expanding this gives the normal equations:

This is always a consistent system. If has full column rank (columns are linearly independent), then is invertible and the unique least-squares solution is:

1.3.1 Derivation via Calculus (Alternative Approach)

We can also derive the normal equations by minimizing directly. Expanding:

Taking the gradient and setting it to zero:

This confirms the normal equations from a calculus perspective.

1.3.2 Properties of

The matrix is always:

• Square:
• Symmetric:
• Positive semi-definite:
• Invertible if and only if has full column rank (columns linearly independent)

1.3.3 The Pseudoinverse

When has full column rank, the formula can be written compactly using the Moore–Penrose pseudoinverse:

so that . The pseudoinverse generalizes the ordinary inverse: when is square and invertible, ; for rectangular with full column rank it gives the least-squares solution directly. It satisfies the four Moore–Penrose conditions, and in particular and .

The pseudoinverse is central to numerical linear algebra and appears throughout machine learning and signal processing as the canonical way to “invert” a non-square or rank-deficient mapping.

1.4 Projection Matrices

1.4.1 Projection onto a Subspace

For a subspace , the projection of onto is the unique vector closest to . The key property is that the error is orthogonal to .

When (column space of ), the projection of is:

This means we can define a projection matrix such that :

This matrix projects any vector onto the column space .

Special case: projection onto a line. If (a single nonzero vector ), then:

1.4.2 Properties of Projection Matrices

A matrix is an orthogonal projection matrix if and only if it satisfies two conditions:

1. Idempotent: (projecting twice gives the same result as projecting once)
2. Symmetric:

These can be verified for :

• ✓
• ✓ (using symmetry of )

Additional properties:

• For any ,
• is also a projection matrix, projecting onto (the left null space, orthogonal complement of )
• is not invertible. The projection matrix projects every vector in onto the column space , which has dimension (assuming is not square of full rank). Any vector in the orthogonal complement satisfies , so has a nontrivial null space and is therefore singular (not invertible). Geometrically, collapses the entire orthogonal complement to zero, making it impossible to recover the original vector from alone.

1.4.3 Proof that for Projection onto a Line

For :

The scalar in the middle cancels with one factor in the denominator.

1.5 Data Fitting with Least Squares

1.5.1 Fitting a Line

Given data points , we want to find the best-fit line . Setting up the overdetermined system :

The least-squares solution via normal equations gives the best-fit line.

Key fact: The best-fit line always passes through the point of averages where and .

Proof. The first row of the normal equations corresponds to the first column of (the all-ones vector ):

Dividing both sides by :

This is precisely the condition that the line passes through .

1.5.2 Fitting a Plane and Higher Dimensions

The same idea extends to fitting higher-dimensional surfaces. To fit a plane to data points :

The normal equations still apply, now giving a system for three unknowns.

1.6 QR Decomposition for Least Squares

1.6.1 Why QR is Better

Solving the normal equations via is mathematically valid but can be numerically unstable. The condition number of is the square of the condition number of — meaning small errors in or can be amplified dramatically.

The QR decomposition avoids forming entirely, giving a more stable computation.

1.6.2 Derivation

Factor as where is with orthonormal columns () and is upper triangular with positive diagonal entries. Substituting into the normal equations:

If is invertible (i.e., has full column rank), multiply by :

1.6.3 Solving via Back Substitution

Since is upper triangular, the system is solved efficiently by back substitution — no matrix inversion needed. The algorithm is:

1. Compute the QR decomposition: (using Gram-Schmidt or Householder reflections)
2. Compute
3. Solve by back substitution

Advantages over normal equations:

• No need to form (avoids squaring the condition number)
• Back substitution is efficient ( instead of for inversion)
• Numerically stable and preferred in practice

1.6.4 SVD as an Alternative for Large or Rank-Deficient Problems

For large-scale or rank-deficient problems, the Singular Value Decomposition (SVD) provides the most general and numerically robust approach to least squares. Any matrix can be factored as:

where and are orthogonal matrices and is diagonal with non-negative entries (the singular values of ). The pseudoinverse of is then:

where replaces each nonzero singular value by and leaves zeros in place. The least-squares solution of minimum norm is .

Why SVD over QR or normal equations?

• It handles rank-deficient gracefully (zero singular values are simply ignored).
• It avoids the numerical hazards of forming .
• It reveals the intrinsic geometry (rank, condition number, null space) of the problem.
• It is the method of choice in machine learning (e.g., principal component analysis) and large-scale scientific computing.

The condition number of is ; the condition number of is , which is why working with directly via QR or SVD is preferred over the normal equations for ill-conditioned problems.

---

2. Definitions

• Overdetermined System: A system with more equations than unknowns (); usually has no exact solution.
• Least-Squares Solution: The vector that minimizes , i.e., the sum of squared residuals.
• Residual (Error) Vector: ; the difference between the observed values and the model’s predictions. In a least-squares solution, .
• Normal Equations: The system , whose solution gives the least-squares solution. Derived from the orthogonality condition .
• Projection onto a Subspace: For a subspace , the projection of onto is the unique vector minimizing . The error is orthogonal to .
• Projection Matrix: A matrix such that is the orthogonal projection of onto a subspace. For projection onto : . Characterized by (idempotent) and (symmetric).
• Idempotent Matrix: A matrix satisfying . Applying the projection twice gives the same result as applying it once.
• Pseudoinverse (Moore-Penrose left inverse): For a matrix with full column rank, . It satisfies and gives the least-squares solution .
• Point of Averages: The center point through which every least-squares best-fit line passes, where and are the means of the independent and dependent variable values, respectively.
• QR Decomposition: A factorization where is with orthonormal columns () and is upper triangular with positive diagonal entries.
• Full Column Rank: A matrix has full column rank if , i.e., its columns are linearly independent. This guarantees is invertible and the least-squares solution is unique.

---

3. Formulas

• Normal Equations:
• Least-Squares Solution (when has full column rank):
• Projection of onto :
• Projection Matrix onto :
• Projection onto a Line (spanned by vector ): ,
• Complementary Projection (onto left null space): , where projects onto
• Projection Matrix Properties: (idempotent) and (symmetric)
• QR Least-Squares System: (solved by back substitution)
• Computing from and :
• Residual Norm (minimum error):
• Normal Equations for Line Fitting ():
• Pseudoinverse: (left inverse when has full column rank)

---

4. Practice

4.1. Is the Projection Matrix Invertible? (Lab 5, Task 1)

Is the projection matrix invertible? Why or why not?

Click to see the solution

Key Concept: The rank of an outer product is always 1 (for nonzero ), because every column is a scalar multiple of .

The matrix has the form:

Every column of is a scalar multiple of , so the columns are linearly dependent. Therefore:

• (for )
• The columns are linearly dependent, making

Answer: No, is not invertible. Its rank is 1, so it has a nontrivial null space (all vectors orthogonal to are mapped to zero). A non-square or rank-deficient matrix cannot be invertible.

4.2. Projection onto a Line and its Perpendicular (Lab 5, Task 2)

Let .

(a) Find the projection matrix onto the line through , and also the matrix that projects onto the line perpendicular to .

(b) Compute and , and explain the results.

Click to see the solution

Key Concept: Two complementary projection matrices onto perpendicular lines must sum to and compose to .

(a) Finding and :

For , compute :

The line perpendicular to in has direction (rotate 90°). Then :

(b) Sum and product:

Explanation: Since and project onto two perpendicular subspaces that together span , their sum must recover the full identity (any vector = its part along + its part perpendicular to ). Their product is zero because projecting onto one line and then its perpendicular gives the zero vector.

Answer: , , , .

4.3. Least Squares to Fit a Plane (Lab 5, Task 3)

We want to fit a plane to the following 4 data points:

3	1	1
5	2	1
6	0	3
0	0	0

(a) Find the (overdetermined) system with 4 equations and 3 unknowns.

(b) Set up and solve the normal equations .

Click to see the solution

Key Concept: Substitute each data point into the plane equation to get one row per data point, then apply the least-squares formula.

(a) Setting up :

Substituting each into :

(b) Setting up the normal equations:

Compute and :

The normal equations are:

Solving (using the inverse of ):

Answer: The best-fit plane is .

4.4. Projection of onto the Column Space of (Lab 5, Task 4)

Find the projection of onto the column space of :

Split into , with in and orthogonal to . Identify which fundamental subspace contains .

Click to see the solution

Key Concept: The projection where . The complementary part lies in .

1. Compute and its inverse:

2. Compute the projection matrix :

3. Compute :

4. Compute :

5. Identify the subspace for : Since is orthogonal to , it must lie in (the left null space). Verify: ✓

Answer: , .

4.5. Least Squares Solution and Perpendicularity Verification (Lab 5, Task 5)

Solve by least squares, and find , given:

Verify that the error is perpendicular to the columns of .

Click to see the solution

Key Concept: The least-squares error is always perpendicular to ; verify by checking for each column .

1. Set up and solve the normal equations :

   , so:

2. Compute the projection :

3. Compute the error :

4. Verify orthogonality (let and ):

Answer: , . The error is perpendicular to both columns of .

4.6. Best-Fit Line and the Point of Averages (Lab 5, Task 6)

The data points are , , , . The average time is and the average observation is .

(a) Find the best-fit line and verify it passes through .

(b) Explain algebraically why always holds for the least-squares line.

Click to see the solution

Key Concept: The least-squares line always passes through the center of mass (point of averages) of the data. This follows directly from the first normal equation.

(a) Finding the best-fit line:

The design matrix and observation vector are:

Compute the normal equation components:

Solving the system gives , .

Check: ✓

(b) Algebraic explanation:

The first normal equation comes from the first row of :

Dividing both sides by :

This proves that the least-squares line always passes through the point of averages .

Answer: Best-fit line is . It passes through since .

4.7. Least Squares via QR Decomposition (Lab 5, Task 7)

Find the least-squares solution of using the QR decomposition, given:

with QR decomposition:

Click to see the solution

Key Concept: With QR decomposition , the least-squares system reduces to , solvable by back substitution.

1. Compute :

2. Solve by back substitution:

   The system is:

   • From row 3:
   • From row 2:
   • From row 1:

Answer:

4.8. Orthogonal Basis via Gram-Schmidt (Assignment 5, Task 1)

Given vectors and that span a subspace , apply the Gram-Schmidt process to find an orthogonal basis for .

Click to see the solution

Key Concept: Gram-Schmidt successively removes the component of each new vector that lies along previously computed orthogonal vectors:

1. Set .
2. Compute the projection coefficient:
3. Subtract the projection:
4. Verify orthogonality:

Answer: An orthogonal basis for is .

4.9. Orthogonal Basis Construction (Assignment 5, Task 2)

Given and , find an orthogonal basis for .

Click to see the solution

1. Set .
2. Compute the projection coefficient:
3. Subtract the projection:
4. Verify: ✓

Answer: An orthogonal basis for is .

4.10. Orthogonal Basis Construction in (Assignment 5, Task 3)

Given and , find an orthogonal basis for their span.

Click to see the solution

1. Set , with .

2. Compute projection coefficient:

3. Subtract the projection:

   From the assignment: .

4. Verify: ✓

Answer: An orthogonal basis for is .

4.11. Orthogonal Basis Construction with Parameters (Assignment 5, Task 4)

Given and , find an orthogonal basis.

Click to see the solution

1. Set .
2. Compute the projection coefficient:
3. Subtract the projection ():
4. Verify: ✓

Answer: An orthogonal basis is .

4.12. Orthogonal Basis in (Assignment 5, Task 5)

Given and , apply Gram-Schmidt to find an orthogonal basis for their span.

Click to see the solution

1. Set .
2. Compute projection coefficient:
3. Subtract the projection:
4. Verify: ✓

Answer: An orthogonal basis is .

4.13. Orthogonal Basis in with Three Vectors (Assignment 5, Task 6)

Given and , find an orthogonal basis.

Click to see the solution

1. Set , with .
2. Compute projection coefficient:
3. Subtract the projection:
4. Verify: ✓

Answer: An orthogonal basis is .

4.14. Compute from and (Assignment 5, Task 7)

Given that and are known, compute for:

Click to see the solution

Key Concept: In QR decomposition, since .

Computing entry by entry:

Answer:

4.15. Compute from and for a Second Matrix (Assignment 5, Task 8)

Given:

Compute .

Click to see the solution

Answer:

4.16. Normal Equations and Least-Squares Solution (Assignment 5, Task 9)

For the system where and :

(a) Write the normal equations .

(b) Find the least-squares solution .

Click to see the solution

1. Compute and :

(a) The normal equations are:

(b) Compute :

Answer:

4.17. Solve a Least-Squares Problem via the Normal Equations (Assignment 5, Task 10)

For and :

(a) Write the normal equations. (b) Find .

Click to see the solution

1. Compute:

(a) Normal equations:

(b)

Answer:

4.18. Derive the Normal Equations for a Data-Fitting Problem (Assignment 5, Task 11)

For and :

(a) Write the normal equations. (b) Find .

Click to see the solution

(a) Normal equations:

(b)

Answer:

4.19. Solve a Second Least-Squares Problem via the Normal Equations (Assignment 5, Task 12)

For and :

(a) Write the normal equations. (b) Find .

Click to see the solution

(a) Normal equations:

(b)

Answer:

4.20. Least-Squares Solution with a Free Variable (Assignment 5, Task 13)

Find all least-squares solutions of where and yield the augmented normal equation matrix:

Click to see the solution

Key Concept: When is not invertible (columns of are linearly dependent), the normal equations have infinitely many solutions, parametrized by free variables.

From the reduced row echelon form, is a free variable. Setting :

• From row 2:
• From row 1:

All least-squares solutions have the form:

Answer: for any .

4.21. Least-Squares Solution with a Free Variable for a Second System (Assignment 5, Task 14)

The normal equations reduce to:

Find all least-squares solutions.

Click to see the solution

From the RREF, is free:

Answer: for any .

4.22. Least Squares via QR Decomposition (Assignment 5, Task 15)

Given and , find the least-squares solution of .

Click to see the solution

Key Concept: With QR decomposition, solve by back substitution.

Answer:

4.23. Least Squares via QR Decomposition for a Second System (Assignment 5, Task 16)

Given and , find the least-squares solution.

Click to see the solution

Solve by back substitution:

• From row 2:
• From row 1:

Answer:

4.24. Projection Matrix from a Lecture Example (Lecture 5, Example 1)

Find the projection matrix onto the column space of:

Click to see the solution

Key Concept: The projection matrix onto is .

1. Compute :

2. Compute :

3. Compute the projection matrix :

4. Verify: and ✓ (the matrix is symmetric by inspection)

Answer:

4.25. Best-Fit Line Through Three Points (Lecture 5, Example 2)

Find the best-fit line through the points , , using least squares.

Click to see the solution

Key Concept: Set up the overdetermined system and solve the normal equations .

1. Set up the system :

2. Compute and :

3. Solve the normal equations:

   Using the inverse formula with :

Answer: The best-fit line is .

4.26. Best-Fit Line to Five Data Points (Lecture 5, Example 3)

Fit a line to the data points , , , , .

Click to see the solution

Key Concept: Form the design matrix, compute the normal equations, and solve.

1. Set up :

2. Compute and :

   (since , )

   (since )

3. Solve the normal equations:

   From the second equation: .

   Substituting into the first: .

   Then .

Answer: The least-squares line is .

4.27. No Matrix with Given Row Space and Null Space (Tutorial 5, Task 1)

Prove there is no matrix whose row space contains and whose null space contains .

Click to see the solution

Key Concept: The row space and null space of any matrix are orthogonal complements in :

Let and . Check their dot product:

Since and are not orthogonal, they cannot simultaneously be in the row space and null space of the same matrix.

Answer: No such matrix exists, because any vector in the row space must be orthogonal to any vector in the null space, but .

4.28. Constructing Matrices with Prescribed Subspaces (Tutorial 5, Task 2)

For each case, construct a matrix with the required property or prove it is impossible:

(1) Column space contains and ; null space contains .

(2) Row space contains and ; null space contains .

(3) has a solution and .

(4) Every row is orthogonal to every column ( is not the zero matrix).

(5) The columns add to a column of s; the rows add to a row of s.

Click to see the solution

(1) Possible. We need for , with the two given vectors spanning . Take:

Require :

So works.

(2) Impossible. The row space vectors and the null space vector must be orthogonal:

The second vector in the row space is not orthogonal to the null space vector, so no such matrix exists.

(3) Impossible. means , i.e., . Therefore the first component of every vector in must be 0. For to have a solution, must be in — but its first component is 1, not 0. Contradiction.

(4) Possible. If every row is orthogonal to every column, then (consider: ). A simple example:

Row 1 = , Col 1 = : ✓; Row 1 and Col 2 = : ✓. And . Such matrices (nilpotent) are possible.

(5) Impossible. If columns add to , then (where ), so . If rows add to , then , so (the row space). But , and would need to be orthogonal to itself: . Impossible.

4.29. Smallest Subspace of the Matrix Space (Tutorial 5, Task 3)

Describe the smallest subspace of the matrix space that contains:

(1) and

(2) and

(3)

(4) , , and

Click to see the solution

Key Concept: The smallest subspace containing a set of vectors (or matrices) is the span of those vectors.

(1) All linear combinations . The smallest subspace is the set of matrices with zero bottom row: .

(2) . Any diagonal matrix can be obtained with and . The smallest subspace is the space of diagonal matrices.

(3) All scalar multiples . The smallest subspace is — a 1-dimensional subspace.

(4) Combining all three with coefficients : The system , , always has a unique solution (the coefficient matrix is nonsingular). So the span is the space of all upper triangular matrices.

4.30. Squaring the Projection Matrix (Tutorial 5, Task 4)

Let be the projection matrix onto a line. Show that .

Click to see the solution

Key Concept: The scalar appears in the numerator when multiplying the two matrices, canceling one factor from the denominator.

Since is a scalar (a real number), it can be factored out:

4.31. Best-Fit Line to Four Data Points (Tutorial 5, Task 5)

Find the best straight-line fit (least squares) to the measurements:

Then find the projection of onto the column space of .

Click to see the solution

Key Concept: The least-squares line minimizes total squared vertical errors. The projection formula then gives .

1. Set up the system:

2. Compute and :

   (Check: ; ; ; .)

3. Solve the normal equations:

   The best-fit line is .

4. Find the projection :

   Using the projection formula :

Answer: Best-fit line: . Projection: .

4.32. Projection Matrix onto a Subspace (Tutorial 5, Task 6)

Find the projection matrix onto the space spanned by and .

Click to see the solution

Key Concept: Form the matrix and compute .

1. Form :

2. Compute :

   ( is diagonal because — the columns are already orthogonal!)

3. Compute :

4. Compute :

5. Verify: and ✓

Answer: